МІНІСТЕРСТВО ОСВІТИ та науки УКРАЇНИ Національний УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра систем автоматизованого проектування ПОЯСНЮВАЛЬНА ЗАПИСКА до курсової роботи з дисципліни “Методи і засоби комп’ютерних інформаційних технологій” на тему: “Аналіз та реалізація стиснення даних за допомогою алгоритму ADSM” Допущено до захисту: Виконав: ст.. гр. КН- Дата:___________ Прийняв: Львів 2008 1. Завдання на курсову роботу Проаналізувати методи стисення даних. Розробити програмну реалізацію методу стиснення даних за допомогою алгоритму ADSM. 2. Анотація Дана курсова робота складається з 56-х сторінок, містить 6 таблиць та 6 малюнків, один додаток. Для написання курсової роботи були використані матеріали з 4-х літературних джерел. Метою даної роботи є створення програми стиснення файлів з використанням алгоритму ADSM. 3. Зміст Завдання на курсову роботу.......................................................................….2 Анотація.........................................................................................................….3 Зміст..............................................................................................................….4 Вступ.............................................................................................................….6 Базова термінологія.....................................................................................….7 Моделювання і ентропія.............................................................................….7 Адаптовані і неадаптовані моделі..............................................................….8 Кодування.....................................................................................................….9 Контекстуальні методи моделювання.......................................................….10 Моделі з фіксованим контекстом........................................................….10 Контекстуально-змішані моделі.........................................................…..11 Ймовірність відходу.............................................................................….12 Виключення...........................................................................................…14 Алфавіти..............................................................................................…...16 Практичні контекстно-обмежені моделі.............................................…16 Реалізація................................................................................................…17 Інші методи статичного моделювання...........................................................18 10.1 Моделі станів............................................................................................18 10.1.1 Динамічне стиснення Маркова………………………………………19 10.2 Граматичні моделі………………………………………………………21 10.3 Моделі новизни…………………………………………………………22 10.4 Моделі для стиснення зображень……………………………………...22 11.Словникові методи…………………………………………………………....22 11.1 Стратегія розбору……………………………………………………….23 11.2 Статичні словникові кодувальники……………………………………24 11.3 Напівадаптоване словникове кодування………………………………24 11.4 Адаптоване словникове кодування: метод Зіва-Лемпела…………….25 11.4.1 LZ77………………………………………………………………...26 11.4.2 LZR……………………………………………………………….…27 11.4.3 LZSS………………………………………………………………...28 11.4.4 LZB………………………………………………………………….28 11.4.5 LZH………………………………………………………………….28 11.4.6 LZ78…………………………………………………………………28 11.4.7 LZW…………………………………………………………………30 11.4.8 LZC………………………………………………………………….30 11.4.9 LZT………………………………………………………………….30 11.4.10 LZMV……………………………………………………………...31 11.4.11 LZJ…………………………………………………………………31 11.4.12 LZFG………………………………………………………….…...31 11.4.13 Структури даних для методу Зіва...